Capacity planning for packet networks is required to provide adequate quality-of-service. A variety of software tools in the current art can be used for this purpose. One vendor that provides such tools is the Wide Area Network Design Laboratory. A description of their products is available at http://www.wandl.com. A second vendor is Optimum Network Performance. See http://www.opnet.com for more information about their products. Other vendors also exist.
These products require input that describes the traffic demands on a network. This data can be provided as a matrix that shows the number of bytes and packets transmitted between access routers. It is necessary to report this data separately for each type-of-service. A traffic matrix is a three dimensional matrix T[x][y][z] where x is the index of an ingress access router, y is the index of an egress access router, and z is the type-of-service (TOS). The values of x and y range from 0 to the number of access routers −1. The value of z ranges from 0 to the number of types of service −1.
Alternatively, a capacity planning tool may require a traffic matrix that characterizes the number of bytes and packets transmitted between service nodes. A traffic matrix is a three dimensional matrix T[x][y][z] where x is the index of an ingress service node, y is the index of an egress service node, and z is the type-of-service (TOS). The values of x and y range from 0 to the number of service nodes −1. The value of z ranges from 0 to the number of types of service −1.
A variety of protocols are used to route packets. These protocols are defined in specifications at http://www.ietf.org. For example, the Open Shortest Path First (OSPF) protocol is used to route within an autonomous system as described in RFC 2328, OSPF Version 2, by J. Moy. The Border Gateway Protocol is used to route among autonomous systems as described in RFC 1771, A Border Gateway Protocol, by Y. Rekhter and T. Li. The Border Gateway Protocol is also described in RFC 1772, Application of the Border Gateway Protocol in the Internet, by Y. Rekhter and P. Gross. The Multi-Protocol Label Switching (MPLS) technology is used for traffic engineering as described in RFC 3031 Multiprotocol Label Switching Architecture by Rosen, et. al.
Virtual Private Networks (VPNs) can also be provided on packet networks. VPNs provide secure connectivity among distributed customer sites. MPLS can also be used to provide Virtual Private Networks (VPNs) as described in RFC 2547, BGP/MPLS VPNs, by Rosen and Rekhter. This is also described in RFC 2917, A Core MPLS IP VPN Architecture, by Muthukrishnan and Malis.
Many books describe these protocols as well. For example, Computer Networks, Third Edition, by A. Tanenbaum, Prentice-Hall, 1996 is an excellent reference text. Routing in the Internet, by Christian Huitema, Prentice Hall, 1995 is also valuable. BGP4 Inter-Domain Routing in the Internet, by John Stewart III, Addison-Wesley, 1999 describes BGP-4. See MPLS: Technology and Applications, by Davie and Rekhter, Morgan Kafmann, 2000 for a discussion of that protocol.
Access routers in the current art can be configured to generate records that provide summary information about packet flows. A flow is a sequence of packets from a source to a destination. An access router identifies a flow by examining the packets that enter and/or exit its interfaces. Packets having identical values for source address/port, destination address/port, protocol, type-of-service, and input interface are considered to be part of the same flow.
Flow records contain multiple items (e.g. source address/port, destination address/port, protocol, type-of-service, input interface, output interface). In addition, an access router counts the number of bytes and packets that comprise this flow and includes these values in the flow record. Flow records provide raw data about packet flows through a network.
An access router is configured to transmit flow records to a specific address and port. This occurs when the flow completes. It may also occur multiple times during a flow.
Cisco is a network equipment vendor that provides flow record generation. This feature on their products is called NetFlow. Each Version 5 NetFlow record contains source IP address, destination IP address, source TCP or UDP port, destination TCP or UDP port, next hop router IP address, incoming interface address or index, outgoing interface address or index, packet count, byte count, start of flow timestamp, end of flow timestamp, IP protocol, type-of-service, TCP flags, source autonomous system, destination autonomous system, source subnet, and destination subnet. Other formats are also available. See http://www.cisco.com for a detailed description of this feature.
It is a difficult task to generate traffic matrixes. First, a backbone network that provides connectivity for customer networks may consist of multiple autonomous systems that are connected in a complex topology. There may be alternate paths between a source and destination. Protocols such as OSPF and BGP-4 provide features for load balancing among these alternate paths. Second, the routers that comprise these networks may use a variety of routing protocols. These protocols may have complex interactions. Third, the routing tables can be large. There can be tens of thousands of routes for some protocols such as BGP-4. Fourth, the traffic volumes through a backbone are substantial. Data about packet flows through a router may total several megabytes. Fifth, it can be difficult to determine the best time to measure traffic flows through a backbone network. Traffic may be maximum at some nodes and minimum at others.